'''
https://leetcode.cn/problems/maximal-network-rank/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:

    # 枚举
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        indegree = [0] * n
        graph = [set() for _ in range(n)]
        for u, v in roads:
            graph[u].add(v)
            graph[v].add(u)
            indegree[u] += 1
            indegree[v] += 1
        max_rank = 0
        for u in range(n):
            for v in range(u + 1, n):
                rank = indegree[u] + indegree[v]
                if v in graph[u]:
                    rank -= 1
                max_rank = max(max_rank, rank)
        return max_rank